Multi-processor systems include two or more computer processors that communicate typically over a bus or a general interconnect network. Individual processors may include a memory cache or cache store that is separate from a main system memory that the individual processors can access. Cache memory connected to the processors can enable faster access to data than through direct access from the main system memory. Caches improve performance by reducing latency associated with accessing data on cache hits and by reducing the number of requests to system memory. Caches can be cascaded in a hierarchy. A cache can serve a group of caches, a group of processors, or a single processor.
Coherence protocols can ensure that a processor reading a memory location actually receives correct or true data. Coherence protocols also ensure that system state remains deterministic by supplying rules enabling a single processor to modify any part of the data at one time. If coherence protocols are faulty, inconsistent copies of data can be generated.
Two main types of cache coherence protocols exist including directory-based coherence protocol and broadcast-based coherence protocol. The directory-based coherence protocol associates tags with each line in memory. A broadcast based coherence protocol also associates tags with each memory line. The caches contain tags associated with each memory line in the cache. The tags contain state information indicating ownership or usage of the memory line. The state information enables tracking of how a memory line is shared. Usage information can describe whether the memory line is cached exclusively in a particular processor's cache, whether the memory line is shared by a number of processors, and/or whether the memory line is currently cached by any processor.
A broadcast-based coherence protocol does not use tags in memory but rather has each of the caches snoop broadcast requests to the system. Each cache contains tags associated with each memory line that has been cached. If the cache does not contain a memory line and a request is made, the other caches are snooped to obtain the line in the proper state. Specifically, if a request is made that requires private or exclusive access to a line the snoop instructs all other caches to purge the line and if the line has been modified, the cache holding the modified line must write the line to the memory and/or the requesting cache. If the line is not held modified in any cache and the line is in a cache, the line may be supplied by that cache or may be obtained from memory. If no cache has a copy of the line, the line is supplied from memory.